package BST;

/**
 * 实现 二叉查找树 的增删改查
 *
 * @author Lwh
 * @time 2022/11/11 01:28
 */
public class BSTUtils {
    /**
     * 递归实现BsTree节点删除
     * @param currentNode BST根节点引用
     * @param key 待删除的节点值
     */
    public static <T extends Comparable<T>> void deleteRecursively(BsTreeNode<T> currentNode,T key) {
        if (currentNode == null) {
            return;
        }
        //当前节点键值大于key，去左子树寻找
        if (currentNode.nodeKey.compareTo(key) > 0) {
            deleteRecursively(currentNode.left, key);
        }
        //当前节点键值小于key，去右子树寻找
        if (currentNode.nodeKey.compareTo(key) < 0) {
            deleteRecursively(currentNode.right, key);
        }
        //当前节点键值等于key，处理当前节点
        else {
            //对于第一种情况，左右子树均为空，直接删除
            if (currentNode.right == null && currentNode.left == null) {
                BsTreeNode<T> parent = currentNode.parent;
                //通过父节点来删除节点
                if (parent.left == currentNode) {
                    parent.left = null;
                }
                if (parent.right == currentNode) {
                    parent.right = null;
                }
//                currentNode = null;
            }
            //对于第二种情况，待删除节点只有左子树，用待删除节点的左子树替换待删除节点即可
            else if(currentNode.right == null) {
                BsTreeNode<T> rootLeft = currentNode.left;
                T temp = rootLeft.nodeKey;
                currentNode.left = rootLeft.left;
                currentNode.right = rootLeft.right;
                currentNode.nodeKey = temp;
                //修正parent的引用
                if (currentNode.left.parent != null) {
                    currentNode.left.parent = currentNode;
                }
                if (currentNode.right.parent != null) {
                    currentNode.right.parent = currentNode;
                }
            }
            //对于第三种情况，待删除节点只有右子树，用待删除节点的右子树替换待删除节点即可
            else if (currentNode.left == null){
                BsTreeNode<T> rootRight = currentNode.right;
                T temp = rootRight.nodeKey;
                currentNode.left = rootRight.left;
                currentNode.right = rootRight.right;
                currentNode.nodeKey = temp;
                //修正parent的引用
                if (currentNode.left.parent != null) {
                    currentNode.left.parent = currentNode;
                }
                if (currentNode.right.parent != null) {
                    currentNode.right.parent = currentNode;
                }
            }
            /*
              第四种情况，左右子树都不为空，用待删除节点的直接前驱（或直接后继）
              来代替待删除节点，同时在二叉排序树种对其直接前驱（或直接后继）做删除操作
             */
            else {
                //找到当前节点的中序前驱节点
                BsTreeNode<T> node = currentNode.left;
                while (node.right != null) {
                    node = node.right;
                }
                //节点值替换
                currentNode.nodeKey = node.nodeKey;
                //删除前驱节点
                deleteRecursively(node, node.nodeKey);
            }
        }

    }

    /**
     * 递归实现BsTree插入
     *
     * @param root BST根节点引用
     * @param nodeInserted 待插入的节点引用
     * @return 插入是否成功
     */
    public static <T extends Comparable<T>> boolean insertRecursively(BsTreeNode<T> root,
                                                               BsTreeNode<T> nodeInserted) {
        if (root == null) {
            root = nodeInserted;
            return true;
        }
        if (root.nodeKey.compareTo(nodeInserted.nodeKey) > 0) {
            if (root.left == null) {
                root.left = nodeInserted;
                nodeInserted.parent = root;
                return true;
            } else {
                return insertRecursively(root.left, nodeInserted);
            }
        } else if (root.nodeKey.compareTo(nodeInserted.nodeKey) < 0) {
            if (root.right == null) {
                root.right = nodeInserted;
                nodeInserted.parent = root;
                return true;
            } else {
                return insertRecursively(root.right, nodeInserted);
            }
        } else {
            return false;
        }
    }

    /**
     * 递归实现BsTree查找
     *
     * @param root BST根节点引用
     * @param key  待查找的节点值
     * @return 命中的节点
     */
    public static <T extends Comparable<T>> BsTreeNode<T> searchRecursive(BsTreeNode<T> root, T key) {
        if (root == null) return null;
        if (root.getValue().compareTo(key) > 0) {
            return searchRecursive(root.getLeft(), key);
        } else if (root.getValue().compareTo(key) < 0) {
            return searchRecursive(root.getRight(), key);
        } else {
            return root;
        }
    }
}
